package com.lwx.leetcode.dp;

/**
 * 等和子集
 */
public class equalSubSet416 {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        int sum = 0;
        int n = nums.length;
        int maxEle = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (maxEle > nums[i]) {
                maxEle = nums[i];
            }
        }
        int target = sum / 2;
        if (sum % 2 != 0 || maxEle > target) {
            return false;
        }
        //dp[i][j] 代表 nums[0...i]中存在和,使其为j
        boolean[][] dp = new boolean[n][target + 1];
        dp[0][nums[0]] = true;
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < target + 1; j++) {
                if(j >=nums[i]){
                    //nums[i]既可以放在j位置，也可以不放在j位置
                    dp[i][j] = dp[i-1][j] || dp[i][j-nums[i]];
                }else {
                    //j<nums[i],j位置不可能放nums[i]
                    dp[i][j] = dp[i-1][j];
                }
            }

        }
        return dp[n-1][target];
    }
}
